package leetcode

type unionFind struct {
	root, size []int
	numRoot      int
}

func newUnionFind(n int) (u *unionFind) {
	u = &unionFind{
		root:  make([]int, n),
		size:    make([]int, n),
		numRoot: n,
	}
	for i := 0; i < n; i++ {
		u.root[i] = i
		u.size[i] = 1
	}
	return
}

func (u *unionFind) findRoot(i int) int {	
	if p := u.root[i]; p != i {
		u.root[i] = u.findRoot(p)
	}
	return u.root[i]
}

func (u *unionFind) unite(x, y int) {
	x, y = u.findRoot(x), u.findRoot(y)
	if x == y {
		return
	}
	if u.size[x] < u.size[y] {
		x, y = y, x
	}
	u.root[y] = x
	u.size[x] += u.size[y]
	u.numRoot--
}

func (u *unionFind) isSameRoot(i, j int) bool {
	return u.findRoot(i) == u.findRoot(j)
}